Valid triangle number

Time: O(N^2); Space: O(LogN); medium

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]

Output: 3

Explanation:

  • Valid combinations are:

    • 2,3,4 (using the first 2)

    • 2,3,4 (using the second 2)

    • 2,2,3

Example 2:

Input: nums = [3,3,3]

Output: 1

Explanation:

  • Valid combination is 3,3,3.

Constraints:

  • The length of the given array won’t exceed 1000.

  • The integers in the given array are in the range of [0, 1000].

1. Linear Scan [O(N^2), O(LogN)]

As discussed in the last approach, once we sort the given numsnums array, we need to find the right limit of the index k for a pair of indices (i, j) chosen to find the countcount of elements satisfying nums[i] + nums[j] > nums[k] for the triplet (nums[i], nums[j], nums[k]) to form a valid triangle.

We can find this right limit by simply traversing the index k’s values starting from the index k = j + 1 for a pair (i, j) chosen and stopping at the first value of k not satisfying the above inequality. Again, the countcount of elements nums[k] satisfying nums[i] + nums[j] > nums[k] for the pair of indices (i, j) chosen is given by k - j - 1 as discussed in the Binary Search approach.

Further, as discussed in the last approach, when we choose a higher value of index j for a particular i chosen, we need not start from the index j + 1. Instead, we can start off directly from the value of k where we left for the last index j. This helps to save redundant computations.

[3]:

class Solution1(object):
    """
    Time: O(N^2). Loop of k and j will be executed O(n^2) times in total,
          because, we do not reinitialize the value of k for a new value of j chosen(for the same i).
          Thus the complexity will be O(n^2 + n^2) = O(n^2).
    Space: O(LogN). Sorting takes O(\log n)O(logn) space.
    """
    def triangleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0

        nums.sort()    # Sorting takes O(LogN) space.

        for i in range(len(nums)-2):
            if nums[i] == 0:
                continue
            k = i + 2

            for j in range(i + 1, len(nums)-1):
                while k < len(nums) and nums[i] + nums[j] > nums[k]:
                    k += 1
                result += k - j - 1

        return result

[4]:

s = Solution1()

nums = [2,2,3,4]
assert s.triangleNumber(nums) == 3

nums = [3,3,3]
assert s.triangleNumber(nums) == 1

2. Brute Force [O(N^3), O(1)]

The condition for the triplets (a, b, c) representing the lengths of the sides of a triangle, to form a valid triangle, is that the sum of any two sides should always be greater than the third side alone. i.e. a + b > c, b + c > a, a + c > b.

The simplest method to check this is to consider every possible triplet in the given numsnums array and checking if the triplet satisfies the three inequalities mentioned above. Thus, we can keep a track of the countcount of the number of triplets satisfying these inequalities. When all the triplets have been considered, the countcount gives the required result.

See: https://leetcode.com/problems/valid-triangle-number/solution/

3. Using Binary Search [O(N^2LogN), O(LogN)]

See: https://leetcode.com/problems/valid-triangle-number/solution/